package com.mid;

/**
 * Created by Lxk on 2020/2/23.
 */
public class Solution264 {

    /**
     * dp+三指针解决
     *
     * @param n
     * @return
     */
    public int nthUglyNumber(int n) {
        int[] dp = new int[n];
        int idx2 = 0, idx3 = 0, idx5 = 0;
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            int min = Math.min(dp[idx5] * 5, Math.min(dp[idx2] * 2, dp[idx3] * 3));
            if (min == dp[idx2] * 2) {
                idx2++;
            }
            if (min == dp[idx3] * 3) {
                idx3++;
            }
            if (min == dp[idx5] * 5) {
                idx5++;
            }
            dp[i] = min;
        }
        return dp[n - 1];
    }

}
